1. Field of Invention
This invention relates to methods and apparatus for queue sharing.
2. Description of Related Art
Data transmitted in a network is often placed in a serial queue for routing and forwarding. When the queue is full, new data cannot be received until data already in the queue is transferred out. Thus, data transfer rated is limited by the size of a particular queue. Accordingly, new technology is needed.
This invention provides queue sharing methods and apparatus of a queuing system which includes queues of multiple priorities or classes. When data is received for a class queue and the class queue is full because the class queue cannot meet required performance for the data due to conditions such as memory full, buffer threshold exceeded, unacceptable transmission delay or quality, for example, then the queue is in an overflow condition and the data is overflow data. The queue sharing apparatus processes the overflow data by determining whether the overflow data may be placed in one of the other class queues which are not full or whether the overflow data should be dropped.
Class queues may be ordered from low class to high class. Assuming that higher class queues have higher performance requirements such as bandwidths, end-to-end delay, transmission quality, etc., than lower class queues, then, when lower class queues are full, lower class overflow data may be placed in higher class queues until the higher class queues are full without performance penalty. When higher class queues are full, overflow data from the higher class queues may also be placed in lower class queues. However, to maintain higher class performances, a higher class threshold may be generated for each lower class queue so that if the lower class queue cannot meet a corresponding higher class threshold, the lower class queue is considered full with respect to the higher class data.
If higher class data is placed in a lower class queue and the higher class threshold cannot be met, a decision is made whether the higher class data may be transmitted at below the required performance. If a reduction of the higher class performance is not acceptable, the overflow high class data may be dropped or deleted, for example. Dropping data reduces the quality of the transmission but maintains the bandwidth. Thus, the invention optimizes the utilization of class queues with minimum impact on queue performance such as transmission bandwidth.